ICPC Live Archive/4794 - Sharing Chocolate/tille.cpp

   1 #include <iostream>
   2 #include <stdio.h>
   3 #include <vector>
   4
   5 using namespace std;
   6
   7 vector<int> partiendo( int x, int y, vector<int> a );
   8 vector<int> deformar(  int i, int h, int j, vector<int> a );
   9 int cortes=0;
  10
  11 int main(){
  12   int n, x, y, h, cont=0;
  13   while( scanf("%d",&n) && n!=0 ){
  14     cortes=0; cont++;
  15     vector<int> parts;
  16     h=n; cin >> x >> y;
  17     int num=0;
  18     while(h--){ cin >> num; parts.push_back(num); }
  19     parts=partiendo( x, y, parts );
  20     if( parts.size()==0 && cortes-1<n ) cout << "Case " << cont << ": Yes" << endl;
  21     else cout << "Case " << cont << ": No" << endl;
  22   }
  23   return 0;
  24 }
  25
  26 vector<int> partiendo( int x, int y, vector<int> a ){
  27
  28   if( a.size() == 0 ) return a;
  29   for( int i=0; i< a.size() ; i++ ){
  30     int b=0;
  31
  32     for( int h=i; h< a.size() ; h++ ){
  33       if( h==i ) b+=a[h];
  34       else if( a[i]==a[h] ) b+=a[h];
  35       if( b%x==0 && y-(b/x)>-1 ){ cortes+=(h-i)+1; return partiendo( x, y-(b/x), deformar(i,h,-5,a) ); }
  36       if( b%y==0 && x-(b/y)>-1 ){ cortes+=(h-i)+1; return partiendo( x-(b/y), y, deformar(i,h,-5,a) ); }
  37
  38       for( int j=h+1; j< a.size() ; j++ ){
  39
  40         int s=b;
  41         if( a[i]==a[j] ) s=b+a[j];
  42         if( s%x==0 && y-(s/x)>-1 ){ cortes+=(h-i)+2; return partiendo( x, y-(s/x), deformar(i,h,j,a) ); }
  43         if( s%y==0 && x-(s/y)>-1 ){ cortes+=(h-i)+2; return partiendo( x-(s/y), y, deformar(i,h,j,a) ); }
  44
  45       }
  46     }
  47   }
  48   return a;
  49
  50 }
  51
  52
  53 vector<int> deformar( int i, int h, int j, vector<int> a ){
  54   vector<int> f;
  55   for( int g=0; g<a.size(); g++ ) if( g<i || g>h && g!=j ) f.push_back(a[g]);
  56   return f;
  57 }
  58